Optimal load shedding with aggregates and mining queries.

K%2ASQL a unifying engine for sequence patterns and XML.
A strong interest is emerging in SQL extensions for sequence patterns using Kleene-closure expressions. This burst of interest from both the research community and the commercial world is due to the many database and data stream applications made possible by these extensions, including financial services, RFID-based inventory management, and electronic health systems. In this demo, we will present the K*SQL system that represents a major step forward in this area. K*SQL supports a more expressive language that allows for generalized Kleene-closure queries and also achieves the expressive power of the nested word model, which greatly expands the application domain to include XML queries, software trace analysis, and genomics. In this demo, we first introduce the core features of our language in expressing complex pattern queries over both relational and XML data. We overview the architecture of our unifying engine and its user-friendly interfaces. We also present several K*SQL queries from stock market, XML, software trace analysis and genomic applications.
Scalable architecture and query optimization fortransaction%2Dtime DBs with evolving schemas.

From Regular Expressions to Nested Words Unifying Languages and Query Execution for Relational and XML Sequences.
There is growing interest in query language extensions for pattern matching over event streams and stored database sequences, due to the many important applications that such extensions make possible. The push for such extensions has led DBMS vendors and DSMS venture companies to propose Kleene-closure extensions of SQL standards, building on seminal research that demonstrated the effectiveness and amenability to efficient implementation of such constructs. These extensions, however powerful, suffer from limitations that severely impair their effectiveness in many real-world applications. To overcome these problems, we have designed the K*SQL language and system, based on our investigation of the nested words, which are recent models that generalize both words and trees. K*SQL extends the existing relational sequence languages, and also enables applications from other domains such as genomics, software analysis, and XML processing. At the same time, K*SQL remains extremely efficient, using our powerful optimizations for pattern search over nested words. Furthermore, we show that other sequence languages and XPath can be automatically translated into K*SQL, allowing for K*SQL to be also used as a high-performance query execution back-end for those languages. Therefore, K*SQL is a unifying SQL-based engine for sequence and XML queries, which provides novel optimization techniques for both. 1.
Update Rewriting and Integrity Constraint Maintenance in a Schema Evolution Support System PRISM  .
(MIT), USA working on database and cloud computing collaborating with Prof. Sam Madden (MIT).
Automating Database Schema Evolution in Information System Upgrades.
The complexity, cost, and down-time currently created by the database schema evolution process is the source of incessant problems in the life of information systems and a major stumbling block that prevent graceful upgrades. Furthermore, our studies shows that the serious problems encountered by traditional information systems are now further exacerbated in web information systems and cooperative scientific databases where the frequency of schema changes has increased while tolerance for downtimes has nearly disappeared. The PRISM project seeks to develop the methods and tools that turn this error-prone and time-consuming process into one that is controllable, predictable and avoids down-time. Toward this goal, we have assembled a large testbed of schema evolution histories, and developed a language of Schema Modification Operators (SMO) to express concisely these histories. Using this language, the database administrator can specify new schema changes, and then rely on PRISM to (i) predict the effect of these changes on current applications, (ii) translate old queries and updates to work on the new schema version, (iii) perform data migration, and (iv) generate full documentation of intervened changes. Furthermore, PRISM achieves good usability and scalability by incorporating recent advances on mapping composition and invertibility in the implementation of (ii). The progress in automating schema evolution so achieved provides the enabling technology for other advances, such as light-weight database design methodologies that embrace changes as the regular state of software. While these topics remain largely unexplored, and thus provide rich opportunities for future research, an important area which we have been investigated is that of archival information systems, where PRISM query mapping techniques were used to support flashback and historical queries for database archives under schema evolution.
The PRISM Workwench Database Schema Evolution without Tears.
(MIT), USA working on database and cloud computing collaborating with Prof. Sam Madden (MIT).
Optimal sampling from sliding windows.
A sliding windows model is an important case of the streaming model, where only the most “recent ” elements remain active and the rest are discarded in a stream. The sliding windows model is important for many applications (see, e.g., Babcock, Babu, Datar, Motwani and Widom (PODS 02); and Datar, Gionis, Indyk and Motwani (SODA 02)). There are two equally important types of the sliding windows model – windows with fixed size, (e.g., where items arrive one at a time, and only the most recent n items remain active for some fixed parameter n), and bursty windows (e.g., where many items can arrive in “bursts ” at a single step and where only items from the last t steps remain active, again for some fixed parameter t). Random sampling is a fundamental tool for data streams, as numerous algorithms operate on the sampled data instead of on the entire stream. Effective sampling from sliding windows is a nontrivial problem, as elements eventually expire. In fact, the deletions are implicit; i.e., it is not possible to identify deleted elements without storing the entire window. The implicit nature of deletions on sliding windows does not allow the existing methods (even those that support explicit deletions, e.g., Cormode, Muthukrishnan and Rozenbaum (VLDB 05); Frahling, Indyk and Sohler (SOCG 05)) to be directly “translated ” to the sliding windows model. One trivial approach to overcoming the problem of implicit deletions is that of over-sampling. When k samples are required, the over-sampling method maintains k ′&gt; k samples in the hope that at least k samples are not expired. The obvious disadvantages of this method are twofold: (a) It introduces additional costs and thus decreases the
PRIMA archiving and querying historical data with evolving schemas.
(MIT), USA working on database and cloud computing collaborating with Prof. Sam Madden (MIT).
Event%2DOriented Data Models and Temporal Queries in Transaction%2DTime Databases.
Abstract—Past research on temporal databases has primarily focused on state-based representations and on relational query language extensions for such representations. This led to many different proposals that had did not succeed in making a significant impact on SQL-compliant DBMS. More recently however, there has been significant interest and progress on event sequences, leading to vendor-proposed extensions of SQL standards for pattern queries based on Kleene-closure expressions. In this paper, we first outline these extensions and their uses in dealing with sequence of events, and then show that they can also be used effectively to express more traditional temporal queries, such as coalescing and joins, on state-based representations. Thus, we propose an approach that takes full advantage of the fact that every state-based representation also has a dual representation based on its start-event and its end-event. I.
Windows.
The X Window System, Version 11, is the standard window system on Linux and UNIX systems. X11, designed in 1987, was “state of the art ” at that time. From its inception, X has been a network transparent window system in which X client applications can run on any machine in a network using an X server running on any display. While there have been some significant extensions to X over its history (e.g. OpenGL support), X’s design lay fallow over much of the 1990’s. With the increasing interest in open source systems, it was no longer sufficient for modern applications and a significant overhaul is now well underway. This paper describes revisions to the architecture of the window system used in a growing fraction of desktops and embedded systems 1
Publishing Naive Bayesian Classifiers Privacy without Accuracy Loss.
We address the problem of publishing a Naïve Bayesian Classifier (NBC) or, equivalently, publishing the necessary views for building an NBC, while protecting privacy of the individuals who provided the training data. Our approach completely preserves the accuracy of the original classifier, and thus significantly improves on current approaches, such as randomization or anonymization, which typically degrade accuracy to preserve privacy. Current query-view security checkers address the question of ‘Is the view safe to publish?’-complete). Here instead, we tackle the question of ‘How to make a view safe to publish?’ and propose a linear-time algorithm to publish safe NBCenabling views. We first show that a simple measure that restricts the ratios between the published NBC statistics is sufficient to prevent any breach of privacy. Then, we propose a linear-time algorithm to enforce this measure by producing perturbed statistics that assure both (i) individuals’ privacy, and (ii) a classifier that behaves in the same way as the NBC trained on the original data. By carefully expressing the derived statistics using rational numbers, we can easily produce synthetic (sanitized) datasets. Thus, for any given dataset, we produce another dataset that is secure to publish (w.r.t. a uniform prior) and achieves the same classification accuracy. Finally, we extend our results by providing sufficient conditions to cope with arbitrary (non-uniform prior) distributions, and we validate their effectiveness in practice through experiments on real-world data. and are computationally expensive (often Π p 2 1.
Time Versus Standards A Tale of Temporal Databases.

Managing the History of Metadata in Support for DB Archiving and Schema Evolution.
Abstract. Modern information systems, and web information systems in particular, are faced with frequent database schema changes, which generate the necessity to manage them and preserve the schema evolution history. In this paper, we describe the Panta Rhei Framework designed to provide powerful tools that: (i) facilitate schema evolution and guide the Database Administrator in planning and evaluating changes, (ii) support automatic rewriting of legacy queries against the current schema version, (iii) enable efficient archiving of the histories of data and metadata, and (iv) support complex temporal queries over such histories. We then introduce the Historical Metadata Manager (HMM), a tool designed to facilitate the process of documenting and querying the schema evolution itself. We use the schema history of the Wikipedia database as a telling example of the many uses and benefits of HMM. 1
Verifying and Mining Frequent Patterns from Large Windows over Data Streams.
Abstract — Mining frequent itemsets from data streams has proved to be very difficult because of computational complexity and the need for real-time response. In this paper, we introduce a novel verification algorithm which we then use to improve the performance of monitoring and mining tasks for association rules. Thus, we propose a frequent itemset mining method for sliding windows, which is faster than the state-of-the-art methods—in fact, its running time that is nearly constant with respect to the window size entails the mining of much larger windows than it was possible before. The performance of other frequent itemset mining methods (including those on static data) can be improved likewise, by replacing their counting methods (e.g., those using hash trees) by our verification algorithm. I.
Verifying and Mining Frequent Patterns from Large Windows over Data Streams.
Abstract — Mining frequent itemsets from data streams has proved to be very difficult because of computational complexity and the need for real-time response. In this paper, we introduce a novel verification algorithm which we then use to improve the performance of monitoring and mining tasks for association rules. Thus, we propose a frequent itemset mining method for sliding windows, which is faster than the state-of-the-art methods—in fact, its running time that is nearly constant with respect to the window size entails the mining of much larger windows than it was possible before. The performance of other frequent itemset mining methods (including those on static data) can be improved likewise, by replacing their counting methods (e.g., those using hash trees) by our verification algorithm. I.


Minimizing latency and memory in DSMS a unified approach to quasi%2Doptimal scheduling.
Data Stream Management Systems (DSMSs) must support optimized execution scheduling of multiple continuous queries on massive, and frequently bursty, data streams. Previous approaches on optimizing memory consumption or response time (i.e., latency) usually produce very different algorithms. In this paper, we extend the popular chart-partitioning procedure, which was previously used for memory optimization on simple operator paths, to minimize latency as well as memory on complex query-graphs with tuple-sharing forks. Furthermore, we test the performance of algorithms that only assume knowledge of the average behavior of tuples and operators, against a theoretical one that assumes detailed knowledge on the behavior of individual tuples. These experiments show that the practical algorithms closely approximate the performance of the optimal ones. Categories and Subject Descriptors H.2.4 [Database Management]: Systems—Query processing;
Designing an inductive data stream management system the stream mill experience.
There has been much recent interest in on-line data mining. Existing mining algorithms designed for stored data are either not applicable or not effective on data streams, where real-time response is often needed and data characteristics change frequently. Therefore, researchers have been focusing on designing new and improved algorithms for on-line mining tasks, such as classification, clustering, frequent itemsets mining, pattern matching, etc. Relatively little attention has been paid to designing DSMSs, which facilitate and integrate the task of mining data streams—i.e., stream systems that provide Inductive functionalities analogous to those provided by Weka and MS OLE DB for stored data. In this paper, we propose the notion of an Inductive DSMS—a system that besides providing a rich library of inter-operable functions to support the whole mining process, also supports the essentials of DSMS, including optimization of continuous queries, load shedding, synoptic constructs, and non-stop computing. Ease-of-use and extensibility are additional desiderata for the proposed Inductive DSMS. We first review the many challenges involved in realizing such a system and then present our approach of extending the Stream Mill DSMS toward that goal. Our system features (i) a powerful query language where mining methods are expressed via aggregates for generic streams and arbitrary windows, (ii) a library of fast and light mining algorithms, and (iii) an architecture that makes it easy to customize and extend existing mining methods and introduce new ones. 1.
Temporal queries and version management in XML%2Dbased document archives.
 
Time%2DStamp Management and Query Execution in Data Stream Management Systems.

Improving the accuracy of continuous aggregates and mining queries on data streams under load shedding.
Improving the accuracy of continuous aggregates and mining queries on data streams under load shedding
Graceful database schema evolution the PRISM workbench.
Supporting graceful schema evolution represents an unsolved problem for traditional information systems that is further exacerbated in web information systems, such as Wikipedia and public scientific databases: in these projects based on multiparty cooperation the frequency of database schema changes has increased while tolerance for downtimes has nearly disappeared. As of today, schema evolution remains an error-prone and time-consuming undertaking, because the DB Administrator (DBA) lacks the methods and tools needed to manage and automate this endeavor by (i) predicting and evaluating the effects of the proposed schema changes, (ii) rewriting queries and applications to operate on the new schema, and (iii) migrating the database. Our PRISM system takes a big first step toward addressing this pressing need by providing: (i) a language of Schema Modification Operators to express concisely complex schema changes, (ii) tools that allow the DBA to evaluate the effects of such changes, (iii) optimized translation of old queries to work on the new schema version, (iv) automatic data migration, and (v) full documentation of intervened changes as needed to support data provenance, database flash back, and historical queries. PRISM solves these problems by integrating recent theoretical advances on mapping composition and invertibility, into a design that also achieves usability and scalability. Wikipedia and its 170+ schema versions provided an invaluable testbed for validating PRISM tools and their ability to support legacy queries. 

Managing and querying transaction%2Dtime databases under schema evolution.
The old problem of managing the history of database information is now made more urgent and complex by fast spreading web information systems, such as Wikipedia. Our PRIMA system addresses this difficult problem by introducing two key pieces of new technology. The first is a method for publishing the history of a relational database in XML, whereby the evolution of the schema and its underlying database are given a unified representation. This temporally grouped representation makes it easy to formulate sophisticated historical queries on any given schema version using standard XQuery. The second key piece of technology is that schema evolution is transparent to the user: she writes queries against the current schema while retrieving the data from one or more schema versions. The system then performs the labor-intensive and error-prone task of rewriting such queries into equivalent ones for the appropriate versions of the schema. This feature is particularly important for historical queries spanning over potentially hundreds of different schema versions and it is realized in PRIMA by (i) introducing Schema Modification Operators (SMOs) to represent the mappings between successive schema versions and (ii) an XML integrity constraint language (XIC) to efficiently rewrite the queries using the constraints established by the SMOs. The scalability of the approach has been tested against both synthetic data and real-world data from the Wikipedia DB schema evolution history. 1.

XML version detection.

RFID Data Processing with a Data Stream Query Language.
by
Optimizing Timestamp Management in Data Stream Management Systems.
by
A Flexible Query Graph Based Model for the Efficient Execution of Continuous Queries.
by
Load Shedding for Window Joins on Multiple Data Streams.

Load Shedding in Classifying Multi%2DSource Streaming Data A Bayes Risk Approach.
Monitoring multiple streaming sources for collective decision making presents several challenges. First, streaming data are often of large volume, fast speed, and highly bursty nature. Second, it is impossible to offload classification decisions to individual data sources, each of which lacks full knowledge for the decision making. Hence, the central classifier responsible for decision making may be frequently overloaded. In this paper, we study intelligent load shedding for classifying multi-source data. We aim at maximizing classification quality under resource (CPU and bandwidth) constraints. We use a Markov model to predict the distribution of feature values over time. Then, leveraging Bayesian decision theory, we use Bayes risk analysis to model the variances among different data sources in their contributions to the classification quality. We adopt an Expected Observational Risk criterion to quantify the loss of classification quality due to load shedding, and propose a Best Feature First (BFF) algorithm that greedily minimizes such risk. The effectiveness of the approach proposed is confirmed by experiments. 1
Managing XML Versions and Replicas in a P2P Context.

A data stream language and system designed for power and extensibility.
by
Succinct Sampling on Streams

A data stream language and system designed for power and extensibility.
by
Efficient Temporal Coalescing Query Support in Relational Database Systems.
Abstract. The interest in and user demand for temporal databases have only increased with time; unfortunately, DBMS vendors and standard groups have not moved aggressively to extend their systems with support for transaction-time or valid-time. This can be partially attributed to the expected major R&amp;D costs to add temporal support to RDBMS by directly extending the database engine. The newly introduced SQL:2003 standards have actually significantly enhanced our ability to support temporal applications in commercial database systems. The long recognized problem of coalescing, which is difficult to support in the framework of SQL:1992, can now be effectively supported in RDBMS. In this paper, we investigate alternatives of temporal coalescing queries under temporal data models in RDBMS. We provide an SQL:2003-based query algorithm and a native relational user defined aggregates (UDA) approach – both approaches only require a single scan of the database. We conclude that temporal queries can be best supported by OLAP functions supported in the current SQL:2003 standards. These new findings demonstrate that the current RDBMSs are mature enough to directly support efficient temporal queries, and provide a new paradigm for temporal database research and implementation. 1
Using XML to Build Efficient Transaction%2DTime Temporal Database Systems on Relational Databases.

Unifying the Processing of XML Streams and Relational Data Streams.
Relational data streams and XML streams have previously provided two separate research foci, but their unified support by a single Data Stream Management System (DSMS) is very desirable from an application viewpoint. In this paper, we propose a simple approach to extend relational DSMSs to support both kinds of streams efficiently. In our Stream Mill system, XML streams expressed as SAX events, can be easily transformed into relational streams, and vice versa. This enables a close cooperation of their query languages, resulting in great power and flexibility. For instance, XQuery can call functions defined in our SQLbased Expressive Stream Language (ESL) using the logical/physical windows that have proved so useful on relational data streams. Many benefits are also gained at the system level, since relational DSMS techniques for load shedding, memory management, query scheduling, approximate query answering, and synopsis maintenance can now be applied to XML streams. Moreover, the many FSA-based optimization techniques developed for XPath and XQuery can be easily and efficiently incorporated in our system. Indeed, we show that YFilter, which is capable of efficiently processing multiple complex XML queries, can be easily integrated in Stream Mill via ESL user-defined and systemdefined aggregates. This approach produces a powerful and flexible system where relational and XML streams are unified and processed efficiently. 1
Bridging relational database history and the web the XML approach.

Supporting complex queries on multiversion XML documents.
Managing multiple versions of XML documents represents a critical requirement for many applications. Recently, there has been much work on supporting complex queries on XML data (e.g., regular path expressions, structural projections, etc.). In this paper, we examine the problem of implementing efficiently such complex queries on multiversion XML documents. Our approach relies on a numbering scheme whereby durable node numbers (DNNs) are used to preserve the order among the nodes of the XML tree while remaining invariant with respect to updates. Using the document’s DNNs, we show that many complex queries are reduced to combinations of range version retrieval queries. We thus examine three alternative storage organizations/indexing schemes to efficiently evaluate range version retrieval queries in this environment. A thorough performance analysis is then presented to reveal the advantages of each scheme.
Data cleaning using belief propagation.

Mining Databases and Data Streams with Query Languages and Rules.
Abstract. Among data-intensive applications that are beyond the reach of traditional Data Base Management Systems (DBMS), data mining stands out because of practical importance and the complexity of the research problems that must be solved before the vision of Inductive DBMS can become a reality. In this paper, we first discuss technical developments that have occurred since the very notion of Inductive DBMS emerged as a result of the seminal papers authored by Imielinski and Mannila a decade ago. The research progress achieved since then can be subdivided into three main problem subareas as follows: (i) language (ii) optimization, and (iii) representation. We discuss the problems in these three areas and the different approaches to Inductive DBMS that are made possible by recent technical advances. Then, we pursue a languagecentric solution, and introduce simple SQL extensions that have proven very effective at supporting data mining. Finally, we turn our attention to the related problem of supporting data stream mining using Data Stream Management Systems (DSMS) and introduce the notion of Inductive DSMS. In addition to continuous query languages, DSMS provide support for synopses, sampling, load shedding, and other built-in functions that are needed for data stream mining. Moreover, we show that Inductive DSMS can be achieved by generalizing DSMS to assure that their continuous query languages support efficiently data stream mining applications. Thus, DSMS extended with inductive capabilities will provide a uniquely supportive environment for data stream mining applications. 1
Improving Mining Quality by Exploiting Data Dependency.

An Adaptive Nearest Neighbor Classification Algorithm for Data Streams.
Abstract. In this paper, we propose an incremental classification algorithm which uses a multi-resolution data representation to find adaptive nearest neighbors of a test point. The algorithm achieves excellent performance by using small classifier ensembles where approximation error bounds are guaranteed for each ensemble size. The very low update cost of our incremental classifier makes it highly suitable for data stream applications. Tests performed on both synthetic and real-life data indicate that our new classifier outperforms existing algorithms for data streams in terms of accuracy and computational costs. 1
Version Management and Historical Queries in Digital Libraries.

A native extension of SQL for mining data streams.

Version Management and Historical Queries in Digital Libraries.


Temporal XML%3F SQL Strikes Back%21
While the introduction of temporal extensions into database standards has proven difficult to achieve, the newly introduced SQL:2003 and XML/XQuery standards have actually enhanced our ability to support temporal applications in commercial database systems. We illustrate this point by discussing three approaches that use temporally grouped representations. We first compare the approaches at the logical level using a common set of queries; then we turn to the physical level and discuss our ArchIS system that supports the three different approaches efficiently in one unified physical implementation. We conclude that the approaches of managing transaction-time information using XML and SQL can be integrated and supported efficiently within the current standards, and claim that the proposed approach can be extended to valid-time and bitemporal databases. 1.

An XML%2DBased Approach to Publishing and Querying the History of Databases.
There is much current interest in publishing and viewing databases as XML documents. The general benefits of this approach follow from the popularity of XML and the tool set available for visualizing and processing information encoded in this universal standard. In this paper, we explore the additional and unique benefits achieved by this approach on temporal database applications. We show that XML with XQuery can provide surprisingly e#ective solutions to the problem of supporting historical queries on past content of database relations and their evolution. Indeed, using XML, the histories of database relations can be naturally represented by temporally grouped data models. Thus, we identify mappings from relations to XML that are most conducive to modelling and querying database histories, and show that temporal queries that would be di#cult to express in SQL can be easily expressed in standard XQuery. This approach is very general, insofar as it can be used to store the version history of arbitrary documents and, for relational databases, it also supports queries on the evolution of their schema.
Mining Noisy Data Streams via a Discriminative Model.

XBiT An XML%2DBased Bitemporal Data Model.
Past research work on modelling and managing temporal information has, so far, failed to elicit support in commercial database systems. The increasing popularity of XML and XQuery offers a unique opportunity to change this situation, inasmuch as these support temporal information much better than relational tables and SQL. This is the important conclusion claimed in this paper where we show that valid-time, transaction-time, and bitemporal databases can be naturally viewed in XML using temporally-grouped data models; then we show that complex historical queries, that would be very di#cult to express in SQL on relational tables, can now be easily expressed in standard XQuery on such XML-based representations. We first discuss the management of transaction-time and valid-time histories and then extend our approach to bitemporal histories. The approach can be generalized naturally to support the temporal management of arbitrary XML documents and queries on their version history.
Temporal Information Management Using XML.

An Adaptive Learning Approach for Noisy Data Streams.
Two critical challenges typically associated with mining data streams are concept drift and data contamination. To address these challenges, we seek learning techniques and models that are robust to noise and can adapt to changes in timely fashion. We approach the stream-mining problem using a statistical estimation framework, and propose a fast and robust discriminative model for learning noisy data streams. We build an ensemble of classifiers to achieve timely adaptation by weighting classifiers in a way that maximizes the likelihood of the data. We further employ robust statistical techniques to alleviate the problem of noise sensitivity. Experimental results on both synthetic and real-life data sets demonstrate the effectiveness of this new model learning approach. 1.
Fast and Light Boosting for Adaptive Mining of Data Streams.
Supporting continuous mining queries on data streams requires  algorithms that (i) are fast, (ii) make light demands on memory resources,  and (iii) are easily to adapt to concept drift. We propose a novel boosting  ensemble method that achieves these objectives. The technique is based on  a dynamic sample-weight assignment scheme that achieves the accuracy of  traditional boosting without requiring multiple passes through the data. The  technique assures faster learning and competitive accuracy using simpler  base models. The scheme is then extended to handle concept drift via change  detection. The change detection approach aims at significant data changes  that could cause serious deterioration of the ensemble performance, and  replaces the obsolete ensemble with one built from scratch. Experimental results  confirm the advantages of our adaptive boosting scheme over previous approaches.
Query Languages and Data Models for Database Sequences and Data Streams.
We study the fundamental limitations of relational  algebra (RA) and SQL in supporting  sequence and stream queries, and present effective  query language and data model enrichments  to deal with them. We begin by observing  the well-known limitations of SQL in  application domains which are important for  data streams, such as sequence queries and  data mining. Then we present a formal proof  that, for continuous queries on data streams,  SQL su#ers from additional expressive power  problems. We begin by focusing on the notion  of nonblocking (NB) queries that are the only  continuous queries that can be supported on  data streams. We characterize the notion of  nonblocking queries by showing that they are  equivalent to monotonic queries. Therefore  the notion of    for RA can be  formalized as its ability to express all monotonic  queries expressible in RA using only the  monotonic operators of RA. We show that RA  is not  NB-complete,  and SQL is not more  powerful than RA for monotonic queries.
Expressing and optimizing sequence queries in database systems.
this paper, we investigate the design and optimization of a query language capable of expressing and supporting efficiently the search for complex sequential patterns in database systems. Thus, we first introduce SQL-TS, an extension of SQL to express these patterns, and then we study how to optimize the queries for this language. We take the optimal text search algorithm of Knuth, Morris and Pratt, and generalize it to handle complex queries on sequences. Our algorithm exploits the interdependencies between the elements of a pattern to minimize repeated passes over the same data. Experimental results on typical sequence queries, such as double bottom queries, confirm that substantial speedups are achieved by our new optimization techniques
ATLaS A Native Extension of SQL for Data Mining.

Design and Implementation of a Temporal Extension of SQL.

ATLaS A Native Extension of SQL for Data Mining.

Incompleteness of Database Languages for Data Streams and Data Mining the Problem and the Cure.

Representing and Querying the Evolution of Databases and their Schemas in XML.
We show that XML views combined with XML query languages can provide surprisingly effective solutions to the problem of representing and querying the evolution of databases---both the evolution of their contents and the evolution of their schemas. Indeed, using XML, the histories of database relations can be represented naturally by means of temporally grouped data models. We show that schema changes and table histories that would be very difficult to represent in relational databases can be easily represented using XML, and also queried using XQuery.
Temporal Queries in XML Document Archives and Web Warehouses.
By storing the successive versions of a document in an incremental fashion, XML repositories and data warehouses achieve (i) the efficient preservation of critical information, and (ii) the ability of supporting historical queries on the evolution of documents and their contents. In this paper, we present efficient techniques for managing multiversion document histories and supporting powerful temporal queries on such documents. Our approach consists in (i) concisely representing the successive versions of a document as an XML document that implements a temporally grouped data model, and (ii) using XML query languages, such as XQuery, to express complex queries on the content of a particular version, and on the temporal evolution of the document elements and their contents. We show that the data definition &amp; manipulation framework of XML &amp; XQuery can support temporal models and historical queries significantly better than the traditional framework of Relational Tables &amp; SQL. To demonstrate this point, we investigate how to express complex queries on the history of relational tables published as XML data.
ATLAS A Small but Complete SQL Extension for Data Mining and Data Streams.
Introduction  DBMSs have long suffered from SQL&#039;s lack of power and extensibility. We have implemented ATLaS [1], a powerful database language and system that enables users to develop complete data-intensive applications in SQL---by writing new aggregates and table functions in SQL, rather than in procedural languages as in current Object-Relational systems. As a result, ATLaS&#039; SQL is Turing-complete [7], and is very suitable for advanced data-intensive applications, such as data mining and stream queries. The ATLaS system is now available for download along with a suite of applications [1] including various data mining functions, that have been coded in ATLaS&#039; SQL, and execute with a modest (20--40%) performance overhead with respect to the same applications written in C/C++. Our proposed demo will illustrate the key features and applications of ATLaS. In particular, we will demonstrate:  .  ATLaS&#039; SQL features, including its native support for user-defined aggregates and table functi
Publishing and Querying the Histories of Archived Relational Databases in XML.
There is much current interest in publishing and viewing databases as XML documents. The general benefits of this approach follow from the popularity of XML and the tool set available for visualizing and processing information encoded in this universal standard. In this paper, we explore the additional and unique benefits achieved by this approach on temporal database applications. We show that XML views combined with XQuery can provide surprisingly effective solutions to the problem of supporting historical queries on past content of database relations and their evolution. Indeed, using XML, the histories of database relations can be naturally represented by temporally grouped data models. Thus, we identify mappings from relations to XML that are most conducive to modeling and querying database histories, and show that temporal queries that would be very difficult to express in SQL can be easily expressed in standard XQuery.
Greedy Algorithms in Datalog
In the design of algorithms, the greedy paradigm provides a powerful tool
A Deductive Database Approach to A.I. Planning.
In this paper, we show that the classical A.I. planning problem can be modelled using simple database constructs with logic-based semantics. The approach is similar to that used to model updates and nondetermism in active database rules. We begin by expressing plans by means of Datalog 1S programs and nondeterministic choice constructs, for which we provide a formal semantics using the concept of stable models. The resulting programs are characterized by a syntactic structure (XY-stratification) that makes them amenable to efficient implementation using compilation and fixpoint computation techniques developed for deductive database systems.
The Deductive Database System LDL  .
This paper describes the    system and the research advances that have enabled its design and development. We begin by discussing the new nonmonotonic and nondeterministic constructs that extend the functionality of the    language, while preserving its model-theoretic and fixpoint semantics. Then, we describe the execution model and the open architecture designed to support these new constructs and to facilitate the integration with existing DBMSs and applications. Finally, we describe the lessons learned by using    on various tested applications, such as middleware and datamining.
Key Constraints and Monotonic Aggregates in Deductive Databases.
We extend the xpoint and model-theoretic semantic of logic programs to inc lude unique key cfi straints in derived relations. This extension inc reases the expressive power of Datalog programs, while preserving their dec)=4RfiM e semantic ande#c6R t implementation. The greater expressive power yields a simplec harac erization for the notion of set aggregates, inc luding the identic) ion of aggregates that are monotonic  with respec to setc ontainment andc an thus be used inrec)R ive logic programs. These new cfi struc ts arec ritic) in many applic8 ions, and produc e simple logic based formulations for cfi plex algorithms that were previously believed to be beyond the realm of decR8VV ivelogic 1 
Extending SQL for Decision Support Applications.

Efficient Complex Query Support for Multiversion XML Documents.
Managing multiple versions of XML documents represents a critical requirement for many applications. Also, there has been much recent interest in supporting complex queries on XML data (e.g., regular path expressions, structural projections, DIFF queries). In this paper, we examine the problem of supporting efficiently complex queries on multiversioned XML documents. Our approach relies on a scheme based on durable node numbers (DNNs) that preserve the order among the XML tree nodes and are invariant with respect to updates. Using the document&#039;s DNNs various complex queries are reduced to combinations partial versio retrieval queries. We examine three indexing schemes to efficiently evaluate partial version retrieval queries in this environment. A thorough performance analysis is then presented to reveal the advantages of each scheme.
Preserving and Querying Histories of XML%2DPublished Relational Databases.
There is much current interest in publishing and viewing database-resident data as XML documents. In fact, such XML views of the database can be easily visualized on web browsers and processed by web languages, including powerful query languages such as XQuery. As the database is updated, its external XML view also evolves. In this paper, we investigate the problem of representing the evolution history of such a view as yet another XML document, whereby the complete history of the database can also be visualized on web browsers, processed by web languages, and queried using powerful query languages such as XQuery. We investigate various approaches used for publishing relational data, and identify and select those which are best for representing and querying database histories. We show that the selected representations make it easy to formulate in XQuery temporal queries that are difficult to express using SQL on database relations. Finally, we discuss briefly the storage organization that can be used to support these queries efficiently.
The ATLaS System and Its Powerful Database Language Based on Simple Extensions of SQL.

Efficient Structural Joins on Indexed XML Documents.
Queries on XML documents typically combine  selections on element contents, and, via path  expressions, the structural relationships between  tagged elements. Structural joins are  used to find all pairs of elements satisfying the  primitive structural relationships specified in  the query, namely, parent child and ancestor  descendant relationships. Efficient support for  structural joins is thus the key to efficient  implementations of XML queries. Recently  proposed node numbering schemes enable the  capturing of the XML document structure us-  ing traditional indices (such as B+-trees or  R-trees). This paper proposes efficient struc-  tural join algorithms in the presence of tag  indices. We first concentrate on using B+-  trees and show how to expedite a structural  join by avoiding collections of elements that  do not participate in the join. We then intro-  duce an enhancement (based on sibling pointers)  that further improves performance. Such  sibling pointers are easily implemented and  dynamically maintainable. We also present a  structural join algorithm that utilizes R-trees.
The Deductive Database System LDL  
This paper describes the    system and the research advances that have enabled its design and development. We begin by discussing the new nonmonotonic and nondeterministic constructs that extend the functionality of the    language, while preserving its model-theoretic and fixpoint semantics. Then, we describe the execution model and the open architecture designed to support these new constructs and to facilitate the integration with existing DBMSs and applications. Finally, we describe the lessons learned by using    on various tested applications, such as middleware and datamining.
Pushing extrema aggregates to optimize logic queries.
In this paper, we explore the possibility of transforming queries with minimum  and maximum predicates into equivalent queries that can be computed more efficiently.
Efficient schemes for managing multiversionXML documents.
Multiversion support for XML documents is needed in many critical applications,  such as software configuration control, cooperative authoring, web information  warehouses, and &#034;e-permanence&#034; of web documents. In this paper, we  introduce e#cient and robust techniques for (i) storing and retrieving, (ii) viewing  and exchanging, and (iii) querying multiversion XML documents. We first  discuss the limitations of traditional version control methods, such as RCS and  SCCS, and then propose novel techniques that overcome their limitations. Initially,  we focus on the problem of managing secondary storage e#ciently, and  introduce an edit-based versioning scheme that enhances RCS with an e#ective  clustering policy based on the concept of page-usefulness. The new scheme  drastically improves version retrieval at the expense of a small (linear) space  overhead. However, the edit-based approach falls short of achieving objectives  (ii) and (iii). Therefore, we introduce and investigate a second scheme, which  is reference-based and preserves the structure of the original document. In the  reference-based approach, a multiversion document can be represented as yet  another XML document, which can be easily exchanged and viewed on the web;  furthermore, simple queries are also expressed and supported well under this representation.
Optimization of Sequence Queries in Database Systems.

Copy%2DBased versus Edit%2DBased Version Management Schemes for Structured Documents.
Managing multiple versions of XML documents and semistructured data represents a problem of growing interest. Traditional version control methods, such as RCS, use edit scripts representing changes in the document to support the incremental reconstruction of different versions. The edit-based approaches have been recently enhanced with a replication scheme called UBCC [2]. UBCC is based on the notion of page usefulness and ensures effective management for multi-version documents in terms of both retrieval and storage cost. These improvements notwithstanding, the edit-based representation suffers from limited generality and flexibility--e.g., it cannot represent changes such as rearranging the document or duplicating parts of its content. To solve these problems, the paper proposes a copy-based UBCC versioning scheme, which also provides a simpler format for the electronic exchange of multi-version documents. With the objective of matching the performance of the edit-based UBCC technique, we develop algorithms that enhance the copy-based UBCC scheme with page usefulness management. We also present results of various experiments that test the storage and retrieval performance of the new copy-based approach, and compare it with that of the edit-based UBCC approach.
Efficient Management of Multiversion Documents by Object Referencing.
Traditional approaches to versioning semistructured information are edit-based, i.e., subsequent document versions are represented by using edit scripts. This paper proposes a reference-based version management scheme that preserves the logical structure of the evolving document through the use of object references. By preserving the document structure among versions the new scheme facilitates more efficient query support. In particular, we examine queries involving projections and selections on the document versions, as well as queries on the document evolution history. Moreover, we show that the proposed scheme provides an effective representation of multiversioned XML documents, both at the transport and exchange levels. In fact, with the reference-based scheme, a document&#039;s history can also be viewed and processed as yet another XML document. Furthermore, we demonstrate the effectiveness of the new scheme at the storage level. In particular, the scheme is enhanced with a usefulness-based page management policy that extends and adapts techniques used in transaction-time databases to ensure efficient clustering of information among versions. An extensive comparison of the reference-based versioning against representations used in temporal databases and persistent object managers depicts the performance advantages of the new approach. Finally it should be noted that reference-based versioning is applicable to other kinds of semistructured information (besides XML documents), and can be used to replace traditional version control schemes, such as the edit-based RCS and the timestamp-based SCCS. 
A Sequential Pattern Query Language for Supporting Instant Data Mining for e%2DServices.

Storing and Querying Multiversion XML Documents using Durable Node Numbers.
Managing multiple versions of XML documents represents an important problem for many traditional applications, such as software configuration control, as well as new ones, such as link permanence of web documents. Research on managing multiversion XML documents seeks to provide efficient and robust techniques for storing, retrieving and querying such documents. In this paper, we present a novel approach to version management that achieves these objectives by a scheme based on Durable Node Numbers and timestamps for the elements of XML documents. We first present efficient storage and retrieval techniques for multiversion documents. Then, we explore the indexing and clustering strategies needed to assure efficient support for complex queries on content and on document evolution. 1
Storing and Querying Multiversion XML Documents using Durable Node Numbers.
Managing multiple versions of XML documents represents an important problem for many traditional applications, such as software configuration control, as well as new ones, such as link permanence of web documents. Research on managing multiversion XML documents seeks to provide efficient and robust techniques for storing, retrieving and querying such documents. In this paper, we present a novel approach to version management that achieves these objectives by a scheme based on Durable Node Numbers and timestamps for the elements of XML documents. We first present efficient storage and retrieval techniques for multiversion documents. Then, we explore the indexing and clustering strategies needed to assure efficient support for complex queries on content and on document evolution. 1
Extending stratified datalog to capture complexity classes ranging from P to QH.
This paper presents a unified solution to the problem of extending stratified DATALOG to express database complexity classes ranging from P to QH; QH is the query hierarchy containing the decision problems that can be solved in polynomial time by a deterministic Turing machine using a constant number of calls to an N P-oracle. The solution is based on (i) stratified negation as the core of a simple, declarative semantics for negation, (ii) the use of a “choice ” construct to capture the nondeterminism of stable models in a disciplined fashion, (iii) the ability to bind a query to the lowest complexity level that includes the problem at hand, and (iv) a general algorithm that adapts its behavior to the desired level of complexity required by the query so that exponential time computation is only required for hard problems. 1
Semantics and Expressive Power of Nondeterministic Constructs in Deductive Databases.

XML Document Versioning.

Greedy Algorithms in Datalog.
In the design of algorithms, the greedy paradigm provides a powerful tool
Advances in Database Technology %2D EDBT 2000

Database System Extensions for Decision Support the AXL Approach.

SQLST A Spatio%2DTemporal Data Model and Query Language.
In this paper, we propose a query language and data model  for spatio-temporal information, including objects of time-changing geometry.
User Defined Aggregates in Object%2DRelational Systems.
User-defined aggregates are essential in many advanced database applications, particularly in expressing data mining functions, but they find little support in current systems including Object-Relational databases. Three serious limitations of current systems are (i) the inability of introducing new aggregates (e.g., by coding them in procedural language as originally proposed in SQL3), (ii) the inability of returning partial results during the computation (e.g., to support online aggregation), and (iii) the inability of using aggregates in recursive queries (e.g., to express Bill of Materials and optimized graph searches). In this paper, we presents a unified solution to these problems which realizes SQL3 original proposal for user-defined aggregates (UDAs) , and adds significant improvements in terms of expressive power and ease of use: in fact our SQL-AG system also supports online aggregation, monotonic aggregation, and a high-level aggregate definition language named SADL. We focu...
CMP A Fast Decision Tree Classifier Using Multivariate Predictions.
Most decision tree classifiers are designed to keep class histograms for single attributes, and to select a particular attribute for the next split using said histograms. In this paper, we propose a technique where, by keeping histograms on attribute pairs, we achieve (i) a significant speed-up over traditional classifiers based on single attribute splitting, and (ii) the ability of building classifiers that use linear combinations of values from non-categorical attribute pairs as split criterion. Indeed, by keeping two-dimensional histograms, CMP can often predict the best successive split, in addition to computing the current one; therefore, CMP is normally able to grow more than one level of a decision tree for each data scan. CMP’s performance improvements are also due to techniques whereby non-categorical attributes are discretized without loss in classification accuracy; in fact, we introduce simple techniques, whereby classification errors caused by discretization at one step can then be corrected in the following step. In summary, CMP represents a unified algorithm that extends the functionality of existing classifiers and improves their performance. 1.
Using SQL to Build New Aggregates and Extenders for Object%2D Relational Systems.
User-defined Aggregates (UDAs) provide a  versatile mechanism for extending the power  and applicability of Object-Relational  Databases (O-R DBs). In this paper, we describe  the AXL system that supports an SQLbased  language for introducing new UDAs.  AXL is easy to learn and use for database programmers  because it preserves the constructs,  programming paradigm and data types  of SQL (whereas there is an `impedance  mismatch&#039; between SQL and the procedural  languages of user-defined functions currently  used in O-R DBs). AXL will also inherit the  benefits of database query languages, such as  scalability, data independence and parallelizability.  In this paper, we show that, while  adding only minimal extensions to SQL, AXL  is very powerful and capable of expressing  complex algorithms e#ciently. We demonstrate  this by coding data mining functions  and other advanced applications that, previously,  had been a major problem for SQL  databases.  Due to its flexibility, SQL-compati...
Version Management of XML Documents.
The problem of ensuring efficient storage and fast retrieval  for multi-version structured documents is important because of the recent  popularity of XML documents and semistructured information on  the web. Traditional document version control systems, e.g. RCS, which  model documents as a sequence of lines of text and use the shortest edit  script to represent version differences, can be inefficient and they do not  preserve the logical structure of the original document. Therefore, we propose  a new approach where the structure of the documents is preserved  intact, and their sub-objects are timestamped hierarchically for efficient  reconstruction of current and past versions. Our technique, called the  Usefulness Based Copy Control (UBCC), is geared towards efficient version  reconstruction while using small storage overhead. Our analysis and  experiments illustrate the effectiveness of the overall approach to version  control for structured documents. Moreover UBCC can easily support  multiple concurrent versions as well as partial document retrieval.  1 
Version Management of XML Documents.
The problem of ensuring efficient storage and fast retrieval  for multi-version structured documents is important because of the recent  popularity of XML documents and semistructured information on  the web. Traditional document version control systems, e.g. RCS, which  model documents as a sequence of lines of text and use the shortest edit  script to represent version differences, can be inefficient and they do not  preserve the logical structure of the original document. Therefore, we propose  a new approach where the structure of the documents is preserved  intact, and their sub-objects are timestamped hierarchically for efficient  reconstruction of current and past versions. Our technique, called the  Usefulness Based Copy Control (UBCC), is geared towards efficient version  reconstruction while using small storage overhead. Our analysis and  experiments illustrate the effectiveness of the overall approach to version  control for structured documents. Moreover UBCC can easily support  multiple concurrent versions as well as partial document retrieval.  1 
User%2DDefined Aggregates for Datamining.
User-defined aggregates can be the linchpin of sophisticated datamining functions and other advanced database applications. This is demonstrated by our efficient implementation on DB2 of SQL3 user-defined aggregates extended with early returns, which we have used to implement several data mining algorithms. Aggregates with early returns are monotonic and can thus be used freely in recursive queries. 1 Introduction  The importance of rollups and data cubes in decision support is universally recognized, and these aggregates have now become sine qua non built-ins in the new releases of commercial DBMSs. Yet, we claim that both researchers and vendors have overlooked UserDefined Aggregates (UDA)s, which can play an even more critical and pervasive role in database-centric data mining applications. Indeed, we show that:  ffl Many data mining algorithms rely on specialized aggregates.  ffl The number and diversity of these aggregates implies that (rather than vendors adding ad hoc builtins, ...
User%2DDefined Aggregates in Database Languages.
User-defined aggregates can be the linchpin of sophisticated datamining functions and other advanced database applications, but they find little support in current database systems including Object-Relational databases. Three serious limitations of current databases are (i) the inability of introducing new aggregates (e.g., by coding them in a procedural language as proposed in SQL3), (ii) the inability of returning partial results during computation (e.g., to support online aggregation), and (iii) the inability of using aggregates in recursive queries---e.g., to express Bill of Materials (BoM) applications and optimized graph searches. This paper proposes a unified solution to these problems, and discusses practical and theoretical aspects of this powerful addition to database languages.  1 Introduction  The importance of new specialized aggregates in advanced applications is exemplified by rollups and data cubes that, owing to their use in decision support applications, are now sine ...
User%2DDefined Aggregates in Database Languages.
User-defined aggregates can be the linchpin of sophisticated datamining functions and other advanced database applications, but they find little support in current database systems including Object-Relational databases. Three serious limitations of current databases are (i) the inability of introducing new aggregates (e.g., by coding them in a procedural language as proposed in SQL3), (ii) the inability of returning partial results during computation (e.g., to support online aggregation), and (iii) the inability of using aggregates in recursive queries---e.g., to express Bill of Materials (BoM) applications and optimized graph searches. This paper proposes a unified solution to these problems, and discusses practical and theoretical aspects of this powerful addition to database languages.  1 Introduction  The importance of new specialized aggregates in advanced applications is exemplified by rollups and data cubes that, owing to their use in decision support applications, are now sine ...
Universal Temporal Extensions for Database Languages.
Temporal reasoning and temporal query languages present difficult research problems of theoretical interest and practical importance. One problem is the chasm between point-based temporal reasoning and intervalbased reasoning. Another problem is the lack of robustness and universality in many proposed solutions, whereby temporal extensions designed for one language cannot be easily applied to other query languages--- e.g., extensions proposed for SQL cannot be applied to QBE or Datalog. In this paper, we provide a simple solution to both problems by observing that all query languages support (i) single-value based reasoning and (ii) aggregate-based reasoning, and then showing that these two modalities can be naturally extended to support, respectively, point-based and interval-based temporal queries. We follow TSQL2 insofar as practical requirements are concerned, and show that its functionality can be captured by simpler constructs which can be applied uniformly to Datalog, QBE and SQ...
Grammars and Automata to Optimize Chain Logic Queries.
The critical problem of finding efficient implementations for recursive queries with bound arguments offers many open challenges of practical and theoretical import. In particular, we need methods that are effective for the general case, such as non-linear programs, as well as for specialized cases, such as left-recursive linear programs. In this paper, we propose a novel approach that solves this problem for chain queries, i.e., for queries where bindings are propagated from arguments in the head to arguments in the tail of the rules, in a chain-like fashion. The method, called pushdown method, is based on the fact that each chain query can be associated with a context-free language, and that a pushdown automaton recognizing this language can be emulated by rewriting the query as a particular factorized left-linear program. The proposed method generalizes and unifies previous techniques such as the `counting&#039; and `right-, left-, mixed-linear&#039; methods. It succeeds in reducing many non-linear programs to query-equivalent linear ones.

Universal Temporal Data Languages.
. Temporal reasoning and temporal query languages present difficult research challenges, which are slowly yielding to the combined attack of many investigations motivated by the theoretical interest and practical import of the problem. In this paper, we subscribe to TSQL2 insofar as practical requirements for a query language are concerned, but we propose a solution that overcomes its shortcomings, particularly the lack of universality whereby TSQL2 temporal extensions can not be easily applied to other query languages, such as QBE and Datalog. In this paper, we use Datalog as a framework to develop a new language --- Temporal Data Language (TDL). To support our claim of universality, we argue that TDL constructs and semantics can be directly applied to derive temporal extensions of languages, such as QBE and SQL. Finally, we evaluate alternative approaches to the implementation of TDL, using as the basis for implementation the LDL++ system with extended aggregates developed at UCLA.  ...
User Defined Aggregates for Logical Data Languages.
A new wave of data-intensive and knowledge-based applications---such as data mining and decision support---require the introduction of complex application-specific aggregate functions. In this paper, we propose extensions for deductive database systems to support these new applications. We develop constructs, formal semantics, and implementation techniques for user-defined aggregates, and describe their realization in an extended LDL++ system recently built at UCLA. With these extensions, the system can support online aggregation, roll-ups for data cubing, temporal aggregates for time-series, iceberg queries, and other recently proposed operators used in decision support and data mining procedures. We then discuss the application of this technology to other DBMSs, and in particular to the SQL3 specifications that support the notion of user-defined aggregates. We show that SQL3 suffers from limitations that severely restrict its use in new applications; thus we propose simple extensio...

Greedy Algorithms in Datalog with Choice and Negation.
In the design of algorithms, the greedy paradigm provides a powerful tool for solving efficiently classical computational problems, within the framework of procedural languages. However, expressing these algorithms within the declarative framework of logic-based languages has proven a difficult research challenge. In this paper, we extend the framework of Datalog-like languages to obtain simple declarative formulations for such problems, and propose effective implementation techniques to ensure computational complexities comparable to those of procedural formulations. These advances are achieved through the use of the choice construct, extended with preference annotations to effect the selection of alternative stable-models and nondeterministic fixpoints. We show that, with suitable storage structures, the differential fixpoint computation of our programs matches the complexity of procedural algorithms in classical search and optimization problems. 1 Introduction  The problem of findin...
Advanced Database Systems.
Monet is a customizable database system developed at CWI and University of Amsterdam, intended to be used as the database backend for widely varying application domains. It is designed to get maximum database performance out of today&#039;s workstations and multiprocessor systems. It has already achieved considerable success in supporting a Data Mining application [12, 13], and work is well under way in a project where it is used in a high-end GIS application. Monet is a type- and algebra-extensible database system and employs shared memory parallelism. In this paper, we give the goals and motivation of Monet, and outline its architectural features, including its use of the Decomposed Storage Model (DSM), emphasis on bulk operations, use of main virtual-memory and server customization. As a case example, we discuss some issues on how to build a GIS on top of Monet; amongst others how Monet can handle the very large data volumes involved.   Parts of this work are supported by SION grant no. ...
The Nonmonotonic Semantics of Active Rules in Deductive Databases.
We provide a logic-based semantics for active database rules under the immediately-after, tuple-level activation policy of SQL3. This result allows us to characterize and analyze the behavior of complex rule systems using the declarative framework of stable models, and to lay the theoretical foundation for a very desirable integration of active databases and deductive databases. 1 Introduction  Deductive database research has long recognized, and struggled to resolve, two related problem areas pertaining to the formal semantics of logic-oriented, rulebased systems. The first problem is how to move beyond stratified negation, while preserving computational tractability; the second problem is how to provide simple declarative semantics for updates, and, then, active rules. In fact, there has been much progress on the first front but little on the second front. Indeed, the introduction of concepts such as well-founded models [6] and stable models [4] have established a formal and comprehe...
Temporal Aggregation in Active Database Rules.
An important feature of many advanced active database prototypes is support for rules triggered by complex patterns of events. Their composite event languages provide powerful primitives for event-based temporal reasoning. In fact, with one important exception, their expressive power matches and surpasses that of sophisticated languages offered by Time Series Management Systems (TSMS), which have been extensively used for temporal data analysis and knowledge discovery. This exception pertains to temporal aggregation, for which, current active database systems offer only minimal support, if any. In this paper, we introduce the language TREPL, which addresses this problem. The TREPL prototype, under development at UCLA, offers primitives for temporal aggregation that exceed the capabilities of state-of-the-art composite event languages, and are comparable to those of TSMS languages. TREPL also demonstrates a rigorous and general approach to the definition of composite event language sema...
The Logic of Totally and Partially Ordered Plans A Deductive Database Approach.
this paper, we show that complex planning strategies find natural logic-based formulations and efficient implementations in the framework of deductive database languages. We begin by modeling classical STRIPS-like totally ordered plans by means of Datalog1S programs, and show that these programs have a stable model semantics that is also amenable to efficient computation. We then show that the proposed approach is quite expressive and flexible, and can also model partially ordered plans, which are abstract plans whereby each plan stands for a whole class of totally ordered plans. This results in a reduction of the search space and a subsequent improvement in efficiency. 1 -- Introduction
Programming with Non%2DDeterminism in Deductive Databases.
This paper provides an overview of recent results on this topic with the aim of providing an introduction to the theory and practice of non-determinism in deductive databases. In particular we (i) recall the main results linking non-deterministic constructs in database languages to the theory of data complexity and the expressibility hierarchy of query languages (ii) provide a reasoned introduction to effective programming with nondeterministic constructs (iii) compare the usage of non-deterministic constructs in languages such as
Deterministic and Non%2DDeterministic Stable Models.
Stable models have been first introduced in the domain of total interpretations (T-  stable models), where the existence of multiple T-stable models for the same program provides a powerful mechanism to express non-determinism. Stable models have been later extended to the domain of partial interpretations (P-stable models). In this paper, we show that the presence of multiple P-stable models need not be a direct manifestation of non-determinism, for it can be instead an expression of assorted degrees of undefinedness. To separate the two factors, non-determinism and undefinedness, this paper introduces the notion of deterministic stable models and strictly non-deterministic ones. Deterministic stable models form an interesting family, having a lattice structure where the well-founded model serves as the bottom; the top of the lattice, the maximum deterministic stable model, resolves differences between any two P-stable models in the family. On the other hand, every two models in a fam...
Formal Semantics for Composite Temporal Events in Active Database Rules.
A major thrust of current research in active databases is allowing complex patterns  of temporal events to serve as preconditions for rule triggering. Currently, there is no  common formalism for specifying the semantics of composite events specification languages  and different systems use an assortment of approaches including Finite State Machines,  Petri Nets and Petri Nets. In this paper, we propose a unifying approach, which is based on  a syntax-directed translation of the composite event expressions into Datalog 1S , whose  formal semantics is then used to define the meaning of the original event expressions.
Logic in Databases
Logic and databases have gone a long way together since the  advent of relational databases. Already the first basic query languages for  relational databases beside relational algebra - tuple calculus and domain  calculus - are actually a subset of first order predicate logic. Furthermore  logic proved to be very adequate for establishing a sound theory for relational  databases.  When attempts were made to integrate AI and database technology in  form of expert database systems or knowledge base management systems  logic provided a unifying framework although several differences in the use  of logic in the both fields have been discovered. The confluence of logic  programming and databases triggered deductive databases as new area of  research.  In this overview paper we will discuss shortly the relationship between  relational databases and logic and present the possibilities for coupling  Prolog with databases. The main part of this paper concentrates on deductive  databases, in particular on the database language Datalog. We  conclude by mentioning some facets of recent research on logic and databases.  The goal of this paper is to provide an overview of the most relevant  developments in the field and providing pointers to the literature.  1 
Deductive Databases Challenges

Relating Stable Models and AI Planning Domains.
In this paper, we show that there is a simple connection between logic programming and planning. The main result of this paper is the following: given any planning domain consisting of an initial state, and a set of operation definitions, this domain can be translated, in linear-time, to a logic program such that a given goal G is achievable in the planning domain iff a related goal G  ?  is true in some stable model of the logic program obtained by the translation. We show that this translation yields at least two interesting consequences: (1) methods to update databases can be used to handle surprises when executing plans (i.e. a surprise occurs when an initial plan is partly executed, but one of the resulting intermediate states differs, perhaps due to external reasons, from what is predicted). (2) rigid actions, which are actions that must be executed when their pre-conditions are true, can be easily accommodated within our framework as well. 1 Introduction  One of the fundamental ...
Metaqueries for Data Mining.
This chapter presents a framework that uses metaqueries to integrate inductive learning methods with deductive database technologies in the context of knowledge discovery from databases. Metaqueries are second-order predicates or templates, and are used for (1) Guiding deductive data collection, (2) Focusing attention for inductive learning, and (3) Assisting human analysts in the discovery loop. We describe in detail a system that uses this idea to unify a Bayesian Data Cluster with the Logical Data Language (LDL++), and show the results of three case studies, namely, discovering regularities from a knowledge base, discovering patterns and errors from a large telecommunication database, and discovering patterns and errors from a large chemical database. The patterns discovered using metaqueries are implication rules with probabilities. These rules can link information from many tables in databases, and they can be stored persistently for multiple purposes, including error detection, i...
Polynomial%2DTime Computable Stable Models.

Composite Temporal Events in Active Database Rules A Logic%2DOriented Approach.

Active Database Rules with Transaction%2DConscious Stable%2DModel Semantics.
Semantics represents a major problem area for active databases inasmuch as (i) there is no formal framework for defining an implementationindependent semantics of active rules, and (ii) the various systems developed so far have ad-hoc operational semantics that are widely different from each other. This situation contributes to the difficulty of predicting the run-time behavior of sets of rules: thus, ensuring the termination of a given set of rules is currently viewed as a major research issue. In this paper, we introduce a durable change semantics for active database rules; this semantics improves Starburst&#039;s deferred activation notion with concepts taken from Postgres and Heraclitus and the semantic foundations of deductive databases. We provide a formal logic-based model for this transaction-oriented semantics, show that it is amenable to efficient implementation, and prove that it solves the non-termination problem. 1 Introduction  Several active database languages and systems hav...
The PushDown Method to Optimize Chain Logic Programs %28Extended Abstract%29.
The critical problem of finding efficient implementations for recursive queries with bound arguments offers many open challenges of practical and theoretical import. We propose a novel approach that solves this problem for chain queries, i.e., for queries where bindings are propagated from arguments in the head to arguments in the tail of the rules, in a chain-like fashion. The method, called pushdown, is based on the fact that a chain query can have associated a context-free language and a pushdown automaton recognizing this language can be emulated by rewriting the query as a particular factorized left-linear program. The proposed method generalizes and unifies previous techniques such as the `counting&#039; and `right-, left-, mixed-linear&#039; methods. It also succeeds in reducing many non-linear programs to query-equivalent linear ones.
DATALOG Queries with Stratified Negation and Choice from P to DP.

Relating Stable Models and AI Planning Domains.
In this paper, we show that there is a simple connection between logic programming and planning. The main result of this paper is the following: given any planning domain consisting of an initial state, and a set of operation definitions, this domain can be translated, in linear-time, to a logic program such that a given goal G is achievable in the planning domain iff a related goal G  ?  is true in some stable model of the logic program obtained by the translation. We show that this translation yields at least two interesting consequences: (1) methods to update databases can be used to handle surprises when executing plans (i.e. a surprise occurs when an initial plan is partly executed, but one of the resulting intermediate states differs, perhaps due to external reasons, from what is predicted). (2) rigid actions, which are actions that must be executed when their pre-conditions are true, can be easily accommodated within our framework as well. 1 Introduction  One of the fundamental ...
Intelligent Knowledge Discovery Assistants on the Internet %28Abstract%29.

The Dynamics of Active Database Rules Models and Refinements.
Semantics represents a major problem area for active databases inasmuch as (i) there is no formal framework for defining the abstract semantics of active rules, and (ii) the various systems developed so far have ad-hoc operational semantics that are widely different from each other. This situation contributes to the difficulty of predicting the run-time behavior of sets of rules: thus, ensuring the termination of a given set of rules is currently recognized as a major research issue. This situation hampers the applicability of this powerful technology in critical application areas.
Composite Temporal Events in Active Databases A Formal Semantics
Active databases must support rules triggered by complex patterns of composite temporal events. This paper proposes a general method for specifying the semantics of composite event specification languages. The method is based on a syntax-directed translation of the composite event expressions into Datalo!7s, whose formal semantics is then used to define the meaning of the original event expressions, We show that the method is applicable to languages such aq ODE, Snoop and SAMOS that are baed respectively on the formalisms of Finite State Machines, Even Graphs and Petri Nets. The proposed method overcomes various problems and limitations affecting such formalisms.
Extrema Predicates in Deductive Databases.
A novel approach is proposed for expressing and computing efficiently a large class of problems, including finding the shortest path
VLDB%2794
ion Pattern. In Proceedings of the Twentieth International Conference on Very Large Databases, pages 630--641, Santiago, Chile, 1994. Materialization is a useful abstraction pattern that can be identified in many application settings. Intuitively, materialization is the relationship between a class of categories (e.g., models of cars) and a class of more concrete objects (e.g., individual cars). The talk gives a precise semantic definition of materialization in terms of the usual is-a and is-of abstractions, and of the class/metaclass correspondence. New and powerful inheritance mechanisms are associated with materialization. Examples, properties, and extensions of materialization are also presented. Providing materialization as an abstraction mechanism for conceptual modeling enhances expressiveness by a controled introduction of classification at the application level.  (4) integration of disparate information systems, (5) re-documentation, (6) data quality assessment and assurance,...
Efficient Execution of Recursive Queries Through Controlled Binding Propagation.

Using Metagueries to Integrate Inductive Learning and Deductive Database Technology.

A Simple Model for Active Rules and their Behavior in Deductive Databases.
Recent advances in non-monotonic semantics of deductive databases provide a simple  framework for modeling the even-condition-action rules of active databases. This  approach unifies the semantics of active and deductive databases and yields several benefits.
Expressive Power of Non%2DDeterministic Operators for Logic%2Dbased Languages.
Non-deterministic operators are needed in First-Order relational languages and Datalog to extend the expressive power of such languages and support efficient formulations of low complexity problems. In this paper, we study the operators proposed in the literature, including witness, lazy choice and dynamic choice, and compare their power of expressing deterministic and non-deterministic queries. We obtain a simple hierarchy that relates these operators with each other and with other constructs, such as negation and fixpoint.
On the Unification of Active Databases and Deductive databases.
These two rule-oriented paradigms of databases have been the focus  of extensive research and are now coming of age in the commercial DBMS world.
Negation and Aggregates in Recursive Rules the LDL   Approach.
The problem of allowing non-monotonic constructs, such as negation and aggregates, in recursive programs represents a difficult challenge faced by current research in deductive databases. In this paper, we present a solution that combines generality with efficiency, as demonstrated by its implementation in the new LDL++ system. A novel and general treatment of set aggregates, allowing for user-defined aggregates, is also presented. 1 Introduction  The area of non-monotonic reasoning has benefited significantly from research in deductive databases, as demonstrated by the introduction of the concept of stratified negation and stratified set aggregates [16]. This concept is significant since it removes several of the limitations and problems of Prolog&#039;s negationby -failure, and it is conducive to efficient implementation, as demonstrated by systems such as Glue-Nail, LDL and CORAL [15, 22, 3]. However, as experience was gained with real-life applications [23], it became clear that stratif...
Dynamic Programming Optimization for Logic Queries with Aggregates.

Polynominal Time Computable Stable Models.

A Unified Semantics for Active and Deductive Databases.
These two rule-oriented paradigms of databases have been the focus of extensive research and are now coming of age in the commercial DBMS world. However, the systems developed so far support well only one of the two paradigms---thus limiting the effectiveness of such systems in many applications that require complete integration of both kinds of rules. In this paper, we discuss the technical problems that make such an integration difficult, and trace their roots to a lack of a unified underlying semantics. Then, we review recent advances in the semantics of non-monotonic logic and show that they can be used to unify the foundations of active databases and deductive databases. Finally, we outline the design a new rule language for databases that integrates a deductive system with a trigger-based DBMS. 1 Introduction  Rules provide the main paradigm for expressing computation in active databases and deductive databases. The unification of the two paradigms represents a research problem o...
Using LDL   for Spatio%2DTemporal Reasoning in Atmospheric Science Databases.

Optimization of Linear Logic Programs Using Counting Methods.%
Stochastic Logic Programs (SLPs) have been shown to be a generalisation of Hidden Markov Models (HMMs), stochastic context-free grammars, and directed Bayes&#039; nets. A stochastic logic program consists of a set of labelled clauses p:C where p is in the interval [0,1] and C is a first-order range-restricted definite clause. This paper summarises the syntax, distributional semantics and proof techniques for SLPs and then discusses how a standard Inductive Logic Programming (ILP) system, Progol, has been modified to support learning of SLPs. The resulting system 1) finds an SLP with uniform probability labels on each definition and near-maximal Bayes posterior probability and then 2) alters the probability labels to further increase the posterior probability. Stage 1) is implemented within CProgol4.5, which differs from previous versions of Progol by allowing user-defined evaluation functions written in Prolog. It is shown that maximising the Bayesian posterior function involves ...
A new User%27s Impressions on LDL   and CORAL.

Improving Data Quality Via LDL  .

Using LDL   for Spatio%2DTemporal Reasoning in Atmospheric Science Databases.

Optimization of Linear Logic Programs Using Counting Methods.%
Stochastic Logic Programs (SLPs) have been shown to be a generalisation of Hidden Markov Models (HMMs), stochastic context-free grammars, and directed Bayes&#039; nets. A stochastic logic program consists of a set of labelled clauses p:C where p is in the interval [0,1] and C is a first-order range-restricted definite clause. This paper summarises the syntax, distributional semantics and proof techniques for SLPs and then discusses how a standard Inductive Logic Programming (ILP) system, Progol, has been modified to support learning of SLPs. The resulting system 1) finds an SLP with uniform probability labels on each definition and near-maximal Bayes posterior probability and then 2) alters the probability labels to further increase the posterior probability. Stage 1) is implemented within CProgol4.5, which differs from previous versions of Progol by allowing user-defined evaluation functions written in Prolog. It is shown that maximising the Bayesian posterior function involves ...
Logic Programming Semantics Made Easy.
We propose a new model-theoretic semantics for logic programs,  called pure semantics, based on the notions of unfounded set and assumption  set. The pure semantics emerges from the observation that major  Iogic programming semantics have the following feature in common:  given an &#039;intended model&#039; M, the set of negative literals in M corresponds  exactly with the greatest unfounded set w.r.t. the set of positive literals in  M. In other words, a model contains redundant information as its negative  part can be described in function of its positive part. Thus, the total  models and the partial models of programs can now be characterized by a  set of positive literals. Based on this idea, we develop the pure semantics  for logic programs. The result is a remarkably simple semantics that  unifies previous approaches and explains how partial model semantics follows  from a weaker closed world assumption.
Greedy by Choice.
to graph-computation algorithms. Proposed solutions The greedy paradigm of algorithm design is a well known tool used for efficiently solving many classical computational problems within the framework of procedural languages. However, it is very difficult to express these algorithms within the declarative framework of logic-based languages. In this paper, we extend the framework of Datalog-like languages to provide simple and declarative formulations of such problems, with computational complexities comparable to those of procedural formulations. This is achieved through the use of constructs, such as least and choice, that have semantics reducible to that of negative programs under stable model semantics. Therefore, we show that the formulation of greedy algorithms using these constructs lead to a syntactic class of programs, called stage-stratified programs, that are easily recognized at compile time. The fixpoint-based implementation of these recursiva pro- grams is very efficient and, combined with suitable storage structures, yields asymptotic complexities comparable to those obtained using procedural languages.
Intelligent Databases Old Challenges and New Opportunities.
The evolution of existing information systems and a new wave of data-intensive applications are creating a strong demand for database-centered programming environments much more sophisticated and intelligent than those supported by current database systems. In this paper, we describe the contributions that deductive databases offer to the evolution of databases and information systems to statisfy said demands. In addition to all database essentials, deductive databases support rule-based logic-oriented languages that allow terse formulations of complete applications, along with reasoning and queries. Thus, they support a rule-based interface that eliminates the impedance mismatch problem (between programming language and query sublanguage) and elevates the design and development of database applications to the level of declarative, knowledge-based specifications. In this paper, we review the evolution of the enabling technology and architectures of deductive database prototypes; then w...
Compilation of Set Terms in the Logic Data Language %28LDL%29.

Non%2DDeterminism in Deductive Databases.
This paper examines the problem of adding non-deterministic constructs to a declarative database language based on Horn Clause Logic. We revise a previously proposed approach, the choice construct introduced by Krishnamurthy and Naqvi, from the viewpoints of amenability to efficient implementation and expressive power.
Partial Models and Three%2DValued Models in Logic Programs with Negation.
Properties. In Luis Moniz Pereira and Anil Nerode, editors, Logic Programming and Non-Monotonic Reasoning, Proceedings of the Second International Workshop, pages 43--59. Lisbon, MIT Press, July 1993. [Min82] Jack Minker. On indefinite databases and the closed world assumption. In Proceedings of the 6th Conference on Automated Deduction, New York, pages 292--308. Springer, 1982. [Min88a] Jack Minker. Foundations of Deductive Databases. Morgan Kaufmann, 95 First Street, Los Altos, CA 94022, 1st edition, 1988. [Min88b] Jack Minker. Perspectives in deductive Databases. Journal of Logic Programming, 5:33--60, 1988. [Min89] Jack Minker. Toward a Foundation of Disjunctive Logic Programming. In Ewing L. Lusk and Ross A. Overbeek, editors, Proceedings of the North American Conference on Logic Programming, pages 1215--1235. MIT Press, 1989. [Min91] Jack Minker. An Overview of Nonmonotonic Reasoning and Logic Programming. CS-TR 2736, Computer Science Dept., Univ. Maryland, University of Marylan...
Efficient Processing of Declarative Rule%2DBased Languages for Datebases.

Minimum and Maximum Predicates in Logic Programming.
A novel approach is proposed for ezpressing and computing  efficiently a large class of problems, including  finding the shortest path in a graph, that were previously  considered impervious to an efficient treatment in  the declarative framework of logic-based languages. Our  approach is based on the use of rain and max predicates  having a first-order semantics defined using rules  with negation in their bodies. We show that when cer-  tain monotonictry conditions hold then (1) there ezists  a totM well-founded model for these programs contain-  ing negation, () this model can be computed efciently  using a procedure called greedy flxpoint, and (3) the  original program can be rewritten into a more efficient  one by pushing rain and max predicates into recursion.
Deductive Databases %2D Theory Meets Practice.
Deductive Databases are coming of age with the emergence of efficient and easy to use systems that support queries, reasoning, and application development on databases through declarative logic-based languages. Building on solid theoretical foundations, the field has ben-efited in the recent years form dramatic advances in the enabling technology. This progress is demonstrated by the completion of prototype systems offering such levels of generality, per-formance and robustness that they support well complex application development. Valuable know-how has emerged from the experience of building and using these systems: we have learned about algorithms and architectures for building powerful deductive database systems, and we begin to understand the programming environments and paradigms they are conducive to. Thus, several application areas have been identified where these systems are particularly effective, including areas well beyond the domain of traditional database applications. Finally, the design and deployment of deductive databases has provided new stimulus and a focus to further research into several fundamental issues. As a result, the theory of the field has made significant progress on topics such as semantic extensions to Horn logic and algorithms for compilation and optimization of declarative programs. Thus, a beneficial interaction between theory and practice remains one of the strengths of Deductive Databases as the field is entering the ‘90s and the age of technological maturity. 1
System Analysis for Deductive Database Environments An Enhanced Role for Aggregate Entities.

Deductive Database Systems Applications and Programming.

Stable Models and Non%2DDeterminism in Logic Programs with Negation.
Previous researchers have proposed generalizations of Horn clause logic to support negation and non-determinism as two seperate extensions. In this paper, we show that the stable model semantics for logic programs provides a unified basis for the treatment of both concepts. First, we introduce the concepts of partial models, stable modds, strongly founded models and deterministic models and other interesting classes of partial models and study their relationships. We show that the maximal deterministic model of a program is a subset of the intersection of all its stable models and that the well-founded model of a program is a subset of its maximal deterministic model. Then, we show that the use of stable models subsumes the use of the non-deterministic choice construct in LDL and provides an alternative definition of the semantics of this construct. Finally, we provide a constructive definition for stable models with the introduction of a procedure, called backtracking fixpoint, that noneteterminisfically constructs a total stable model, if such a model exists.
The LDL System Prototype.
The LDL system provides a declarative logic-based language and integrates relational database and logic programming technologies so as to support advanced data and knowledge-based applications. This paper contains a comprehensive overview of the system and contains a description of the LDL language and the compilation techniques employed to translate LDL queries into target queries on the stored data. The paper further contains a description of the architecture and runtime environment of the system and the optimization techniques employed in order to improve the performance and assure the safety of the compiled queries. The paper concludes with an account of the experience gained so far with the system, and discusses application areas where the LDL approach appears to be particularly effective.
Deductive Databases Achievements and Future Directions.
In the recent years, Deductive Databases have been the focus of intense research, which has brought dramatic advances in theory, systems and applications. A salient feature of deductive databases is their capability of supporting a declarative, rule-based style of expressing queries and applications on databases. As such, they find applications in disparate areas, such as knowledge mining from databases, and computer-aided design and manufacturing systems. In this paper, we briefly review the key concepts behind deductive databases and their newly developed enabling technology. Then, we describe current research on extending the functionality and usability of deductive databases and on providing a synthesis of deductive databases with procedural and object-oriented approaches. 1
Object Identity and Inheritance in Deductive Databases %2D an Evolutionary Approach.
This paper proposes simple extensions to logic-based languages for deductive databases to support the key notions of object identity and object inheritance of object-oriented systems. Thus the paper shows how, given a logic program P and its minimal model M(P), it is possible to construct a program/ and its minimal model M(P ) such that M(P&#039;) is basically obtained fr6m M(P) by prefixing each fact of M(P) with a unique identifier. This is accomplished through the use of / non-deterministic choice constructs (or alternatively through negation under the stable model semantics). This allow a user to view facts and predicates of ordinary logic programs as objects and refer to them through their identifiers--in both the exten- sional database and the intensional one. Then, syntactic shorthand conventions are introduced to facilitate reference based reasoning and access to objects. The result is a logic-based language where the ISA inheritance is fully supported along with the use of identifiers as surrogates for the actual objects. The proposed solution is firmly rooted in the theory of deductive databases and simple to implement as an extension of current deductive database systems
Database Transactions in LDL.

Rule Rewriting Methods in the Implementation of the Logic Language LDL.

Optimization in a Logic Based Language for Knowledge and Data Intensive Applications.
This paper describes the optimization approach taken to ensure the safe and efficient execution of applications written in LDL, which is a declarative language based on Horn Clause Logic and in-tended for data intensive and knowledge based applications. In order to generalize the strategy successfully used in relational database systems we first characterize the optimization problem in terms of its execution space, cost functions and search algorithm. Then we extend this framework to deal with rules, complex terms, recursion and various problems resulting from the richer expres-sive power of Logic. Among these is the termination problem (safety), whereby an unsafe execu-tion is treated as an extreme case of poor execution. 1.
Design and Implementation of a Logic Based Language for Data Intensive Applications.

Differential Fixpoint Methods and Stratification of Logic Programs.

Rewriting of Rules Containing Set Terms in a Logic Data Model %28LDL%29.

The Generalized Counting Method for Recursive Logic Queries.
This paper treats the problem of implementing efficiently recursive Horn Clauses queries, including those with function symbols. In particular, the situation is studied where the initial bindings of the arguments in the recursire query goal can be used in the top-down (as in backward chaining) execution phase to improve the efficiency and, often, to guarantee the termination, of the forward chaining execution phase that implements the fixpoint computation for the recursire query. A general method is given for solving these queries; the method performs an analysis of the binding passing behavior of the query, and then reschedules the overall execution as two fixpoint computations derived as results of this analysis. The first such computation emulates the propagation of bindings in the top-down phase; the second generates the desired answer by proving the goals left unsolved during the previous step. Finally, sufficient conditions for safety are derived, to ensure that the fixpoint computations are completed in a finite number of steps.
Control and Optimization Strategies in the Implementation of LDL.

Implementation of Recursive Queries for a Data Language Based on Pure Horn Logic.

Magic Counting Methods.
this paper, we study the problem of efficient implementations of queries on recursire rules without function symbols. We focus on an important subclass, called canonical strongly linear queries (CSL queries), and study the binding-passing property, which entails the propagation of the initial bindings (established by constants in the query goal) during the top-down (as in backward chaining) execu- tion phase
Databases and Logic %2D Forword by the Guest Editor.

An Overview of the LDL System.
This paper presents an overview of data mining techniques in the context of of the deductive-inductive cycle model. The claim made in this paper is that a combination of both of these modes of inference in one model offers adavantages over the exclusive use of either induction or deduction. After an introduction of the model, the paper describes an architecture of the Knowledge Miner environment and its relation to the  LDL++ deductive database technology. In particular, it defines the notion of a meta query and shows how this concept can be used to take advantage of the full power of a deductive data base system. The paper mentions a number of inductive methods that can be used within this framework and describes some data mining experiments performed with the Knowledge Miner.  1 Introduction  Very large collections of data often serve as a corporate resource---to be used for a variety of purposes, many of which are unknown or unspecified at the time of collection. The term Database M...
Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data

Safety and Compilation of Non%2Drecursive Horn Clauses.

Rule Rewriting Methods for Efficient Implementations of Horn Logic.

The Generalized Counting Method for Recursive Logic Queries.
This paper treats the problem of implementing efficiently recursive Horn Clauses queries, including those with function symbols. In particular, the situation is studied where the initial bindings of the arguments in the recursire query goal can be used in the top-down (as in backward chaining) execution phase to improve the efficiency and, often, to guarantee the termination, of the forward chaining execution phase that implements the fixpoint computation for the recursire query. A general method is given for solving these queries; the method performs an analysis of the binding passing behavior of the query, and then reschedules the overall execution as two fixpoint computations derived as results of this analysis. The first such computation emulates the propagation of bindings in the top-down phase; the second generates the desired answer by proving the goals left unsolved during the previous step. Finally, sufficient conditions for safety are derived, to ensure that the fixpoint computations are completed in a finite number of steps.
On the Implementation of a Simple Class of Logic Queries for Databases.
this paper, we study the problem of efficient implementations of queries on recursire rules without function symbols. We focus on an important subclass, called canonical strongly linear queries (CSL queries), and study the binding-passing property, which entails the propagation of the initial bindings (established by constants in the query goal) during the top-down (as in backward chaining) execu- tion phase
Optimization of Nonrecursive Queries.
State-of-the-art optimization approaches for relational database systems, e.g., those used in systems such as OBE, SQL/DS, and commercial INGRES. when used for queries in non-traditional database applications, suffer from two problems. First, the time complexity of their optimization algorithms, being combinatoric, is exponential in the number of relations to be joined in the query. Their cost is therefore prohibitive in situa-tions such as deductive databases and logic oriented languages for knowledge bases, where hundreds of joins may be required. The second problem with the traditional approaches is that, al-beit effective in their specific domain, it is not clear whether they can be generalized to different scenarios (e.g. parallel evalua-tion) since they lack a formal model to define the assumptions and critical factors on which their valiclity depends. This paper
LDL A Logic%2DBased Data Language.
dmontoon, Alberta, Canada, 1992. T6G 2H1. [28] K. G. Waugh, W. H. Williams, Q. Kong, S. Salvini, and G. Chen, &#034;Designing SQUIRREL: an extended SQL for a deductive database system,&#034; The Computer Journal, vol. 33, no. 6, pp. 535--546, 1990. [29] K. Parasaye, M. Chignell, S. Khoshafian, and H. Wang, Intelligent Databases: Object-Oriented, Deductive Hypermedia Technology.  New York, NY: Wiley and Sons Inc., 1989. [30] R. VanDeReit, &#034;Introduction to the special issues in deductive and object-oriented database,&#034; Data and Knowledge Engineering,  vol. 5, pp. 255--261, October 1990. [31] G. DiBattista and M. Lenzerini, &#034;A deductive method for ER modeling,&#034; in  Very Large Databases Proceeding of the Fifteenth International Conference (Amsterdam, The Netherlands August 22-25 1989),  (Palo Alto, CA), pp. 13--21, Morgan Kauknann, 1989. Van DeRiet, R.P. (Ch). [32] J.-W. Han and Z.-N. Li, &#034;Deductive - ER: Deductive entity-relationship data m
Safety and Optimization of Horn Clause Queries.

Issues in the Optimization of a Logic Based Language.

The Representation and Deductive Retrieval of Complex Objects.

Prolog A Database Query Language for All Seasons.

Object Oriented Database Systems and Knowledge Systems.

An Implementation of GEM %2D Supporting a Semantic Data Model on a Relational Back%2DEnd.
Ths paper presents a stmple approach for extendmg the relattonal system INGRES rate one supporting a semanttc data model It describe a DBMS conststmg of O) a user-friendly front-end, supportmg the GEM semanttc data model and query language under the UNIX&#039; tme-sharmg system, and (u) a dedtcated back-end processor provtdmg efSctent support for database transacttons, concurrency control and recovery GEM extends the relattonal model to support the nottons of enttttes wtth surrogates, the relattonshtps of aggregabon and generahzatton, null values and set-valued attributes, and provtdes stmple extenstons of QUEL to handle these new constructs In thts proposed tmplementatton of GEM, the relabonal database processor IDM 500 by Bntton-Lee ts used as the back-end machme  I 
Object%2DOriented Programming in Prolog.

Database Relations with Null Values.
this paper we briefly review some of these issues and then concentrate on the problem of generalizing the formal framework of the relational data model to include null values. A basic problem with null values is that they have many plausible interpretations. The ANSI/SPARC interim report, for instance, cites 14 different manifestations of nulls. Most authors, however, agree that the various manifestations of nulls can be reduced to two basic interpretations. These are: (a) the unknown interpretation: a value exists but it is not known; and lb) the nonexistent interpretation: a value does not exist
The Database Language GEM.

Design of Relational Views over Network Schemas.
An algorithm is presented for designing relational views over network schemas to: (1) support general query and update capability, (2) preserve the information content of the data base and (3) provide independence from its physical organization. The proposed solution is applicable to many existing CCDASYL databases without data or schema conversion. The particular declarations of a CDDASYL schema which supply sources of logical data definition are first identified. Then the view design algorithm is derived on the basis of a formal analysis of the semantic constraints established by these declarations. A new form of data structure diagram is also introduced to visualize these constraints. 1. INTRczaltJcTIm This paper presents a rigorous solution to the problgn of designing relational views &amp;ich support general wery and update capabilities over network schemas. Three objectives are of paramount concern in our approach. They are: 1. information preservation 2. updatability 3. data independence. Let us consider information preservation first. This is needed for supporting general purpose data manipulation capability. Indeed a user must be capable of accessing through views all the information of interest (within his authorization domain). Thus the view must be information-wise equivalent to the underlying schema or that portion of interest. Let us consider now the problem of specifying updates through a view (these include insert delete and modify operations). The simple data organization displayed by a view is often very Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial ad-vantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Assooia-tion for Computing Machinery. To copy otherwise, or to republish, requires a fee end/or specific permission.
Database Relations with Null Values.
this paper we briefly review some of these issues and then concentrate on the problem of generalizing the formal framework of the relational data model to include null values. A basic problem with null values is that they have many plausible interpretations. The ANSI/SPARC interim report, for instance, cites 14 different manifestations of nulls. Most authors, however, agree that the various manifestations of nulls can be reduced to two basic interpretations. These are: (a) the unknown interpretation: a value exists but it is not known; and lb) the nonexistent interpretation: a value does not exist
A Formal Approach to the Definition and the Design of Conceptual Schemata for Database Systems.
This paper presents a rigorous approach to the definition and the design of graphical schemata in the framework of the relational data model. This approach uses and applies various concepts and analytical tools which were presented in a companion paper [33]
A New Normal Form for the Design of Relational Database Schemata.
This paper addresses the problem of database schema design in the framework of the relational data model and functional dependencies. It suggests that both Third Normal Form (3NF) and BoyceCodd Normal Form (BCNF) supply an inadequate basis for relational schema design. The main problem with 3NF is that it is too forgiving and does not enforce the separation principle as strictly as it should. On the other hand, BCNF is incompatible with the principle of representation and prone to computational complexity. Thus a new normal form, which lies between these two and captures the salient qualities of both is proposed. The new normal form is stricter than 3NF, but it is still compatible with the representation principle. First a simpler definition of 3NF is derived, and the analogy of this new definition to the definition of BCNF is noted. This analogy is used to derive the new normal form. Finally, it is proved that Bernstein&#039;s algorithm for schema design synthesizes schemata that are already in the new normal form
On the Design of Relational Database Schemata.
This paper addresses the problem of database schema design in the framework of the relational data model and functional dependencies. It suggests that both Third Normal Form (3NF) and BoyceCodd Normal Form (BCNF) supply an inadequate basis for relational schema design. The main problem with 3NF is that it is too forgiving and does not enforce the separation principle as strictly as it should. On the other hand, BCNF is incompatible with the principle of representation and prone to computational complexity. Thus a new normal form, which lies between these two and captures the salient qualities of both is proposed. The new normal form is stricter than 3NF, but it is still compatible with the representation principle. First a simpler definition of 3NF is derived, and the analogy of this new definition to the definition of BCNF is noted. This analogy is used to derive the new normal form. Finally, it is proved that Bernstein&#039;s algorithm for schema design synthesizes schemata that are already in the new normal form
Mixed Transitivity for Functional and Multivalued Dependencies in Database Relations.
this paper we present a rule, called mixed transitivity, which supplies an alternative and simpler complete axiomatization for the combined functio- nal and multivalued dependencies of database rela-  tions
Decomposition of Relations and Synthesis of Entity%2DRelationship Diagrams.

Multimodel External Schemas for Codasyl Database Management Systems.

Design of Relational Views over Network Schemas.
An algorithm is presented for designing relational views over network schemas to: (1) support general query and update capability, (2) preserve the information content of the data base and (3) provide independence from its physical organization. The proposed solution is applicable to many existing CCDASYL databases without data or schema conversion. The particular declarations of a CDDASYL schema which supply sources of logical data definition are first identified. Then the view design algorithm is derived on the basis of a formal analysis of the semantic constraints established by these declarations. A new form of data structure diagram is also introduced to visualize these constraints. 1. INTRczaltJcTIm This paper presents a rigorous solution to the problgn of designing relational views &amp;ich support general wery and update capabilities over network schemas. Three objectives are of paramount concern in our approach. They are: 1. information preservation 2. updatability 3. data independence. Let us consider information preservation first. This is needed for supporting general purpose data manipulation capability. Indeed a user must be capable of accessing through views all the information of interest (within his authorization domain). Thus the view must be information-wise equivalent to the underlying schema or that portion of interest. Let us consider now the problem of specifying updates through a view (these include insert delete and modify operations). The simple data organization displayed by a view is often very Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial ad-vantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Assooia-tion for Computing Machinery. To copy otherwise, or to republish, requires a fee end/or specific permission.

Review of the ACM%2DSIGMOD International Conference on Management of Data.


